# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/19 9:43 
"""
"""
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

 
 示例 1：


输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


"""

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    class Solution:
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            """
            双指针
            由于我们需要找到倒数第n个节点，因此我们可以使用两个指针first和second
            同时对链表进行遍历，并且first比second超前n个节点。当first遍历到链表末尾时，
            second就恰好处理倒数第n个节点
            """
            dummy = ListNode(0, head)
            first = head
            second = dummy
            for i in range(n):
                first = first.next

            while first:
                first = first.next
                second = second.next

            second.next = second.next.next
            return dummy.next


